package seqlist;


// 车厢类
class DoubleNode {
    // 指向前驱节点
    DoubleNode prev;
    // 存储的具体元素
    int val;
    // 指向后继节点
    DoubleNode next;
    public DoubleNode(int val) {
        this.val = val;
    }
}


/**
 * 基于int的双向链表
 */
public class DoubleLinkedList {
    // 存储的具体车厢个数
    private int size;
    // 头节点
    private DoubleNode first;
    // 尾节点
    private DoubleNode last;

    // 头插
    public void addFirst(int val) {
        // 引入一个局部变量，暂时存储一下头节点的地址
        DoubleNode f = first;
        // 要插入一个节点，首先要new一个节点
        DoubleNode node = new DoubleNode(val);
        first = node;
        if (f == null) {
            last =  node;
        }else {
            node.next = f;
            f.prev = node;
        }
        size ++;
    }

    public void addLast(int val) {
        // 暂存尾节点地址
        DoubleNode l = last;
        DoubleNode node = new DoubleNode(val);
        last = node;
        if (l == null) {
            // 链表为空
            first = node;
        }else {
            node.prev = l;
            l.next = node;
        }
        size ++;
    }

    public void addIndex(int index,int val) {
        // 判断index的合法性
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        else if (index == 0) {
            // 头插
            addFirst(val);
        }
        else if (index == size) {
            // 尾插
            addLast(val);
        }else {
            // 此时0 < index < size
            // 在报错方法上使用alt + enter快捷生成指定方法
            DoubleNode node = node(index);
            // 指向当前位置的前驱节点
            DoubleNode prev = node.prev;
            // 要插入的新节点
            DoubleNode newNode = new DoubleNode(val);
            // 先处理后半部分引用链
            newNode.next = node;
            node.prev = newNode;
            // 再处理前半部分的引用链
            prev.next = newNode;
            newNode.prev = prev;
            size ++;
        }
    }

    /**
     * 根据index索引取得节点值
     * @param index
     * @return
     */
    public int get(int index) {
        if (rangeCheck(index)) {
            DoubleNode node = node(index);
            return node.val;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    public void set(int index,int newVal) {
        if (rangeCheck(index)) {
            DoubleNode node = node(index);
            node.val = newVal;
        }else {
            System.err.println("set index illegal!");
        }
    }

    public void removeValueOnce(int val) {
        // 只需要从头开始遍历
        for (DoubleNode x = first;x != null;x = x.next) {
            if (x.val == val) {
                // 此时X节点就是待删除的节点
                unlinkNode(x);
                return;
            }
        }
    }

    public void removeAllValue(int val) {
        for (DoubleNode x = first;x != null;) {
            if (x.val == val) {
                // x就是待删除的元素
                // 先暂存一下next的节点地址
                DoubleNode next = x.next;
                unlinkNode(x);
                x = next;
            }else {
                x = x.next;
            }
        }
    }

    /**
     * 传入一个双向链表节点，将该节点从双向链表中删除
     * （核心思想:分治，先处理前驱或后继，再处理另一半的情况）
     * @param node
     */
    private void unlinkNode(DoubleNode node) {
        // 待删除节点的前驱
        DoubleNode prev = node.prev;
        // 待删除节点的后继
        DoubleNode next = node.next;
        // 先处理前半部分引用链
        // 判断边界
        if (prev == null) {
            first = next;
        }else {
            // 此时前驱节点不为空
            prev.next = next;
            node.prev = null;
        }
        if (next == null) {
            last = prev;
        }else {
            // 此时后继节点不为空
            next.prev = prev;
            node.next = null;
        }
        size --;
    }


    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    /**
     * 根据index与size的大小关系快速定位指定index位置的节点
     * @param index
     * @return
     */
    private DoubleNode node(int index) {
        // 根据index与size的大小关系来判断到底从头向后走还是从后向前走
        if (index < size >> 1) {
            // 此时从头向后走
            DoubleNode node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }else {
            // 此时index > size / 2
            // 此时从后向前走
            DoubleNode node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(3);
        System.out.println(doubleLinkedList);
        doubleLinkedList.removeAllValue(2);
        // 3
        System.out.println(doubleLinkedList);
    }

    public String toString() {
        String ret = "";
        DoubleNode node = first;
        while (node != null) {
            ret += node.val + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}
